package com.love.common;

/**
 * 最大公约数 和 最小公倍数
 */
public class GCD_LCM {

    // 欧几里得算法来求最大公约数，再利用最大公约数来求最小公倍数

    /**
     * 对于两个非负整数 `a` 和 `b`（假设 `a > b`），其最大公约数可以通过重复取模运算来找到，直到余数为零。基本步骤如下：
     *
     * 1. 如果 `b` 等于 0，那么 `a` 就是 GCD。
     * 2. 否则，将 `a` 替换为 `b`，`b` 替换为 `a % b`（`a` 除以 `b` 的余数）。
     * 3. 重复上述过程，直到 `b` 变为 0。
     */

    // a > b
    // 最大公约数
    public static long gcd(long a,long b){
        return b == 0 ? a : gcd(b, a % b);
    }


    // 最小公倍数
    public static long lcm(long a, long b){
        return (long) a / gcd(a,b) * b;
    }


}
